package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/'>从链表中删去总和值为零的连续节点(Remove Zero Sum Consecutive Nodes from Linked List)</a>
 * <p>给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。</p>
 * <p>删除完毕后，请你返回最终结果链表的头节点。</p>
 * <p>你可以返回任何满足题目要求的答案。(（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）)</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,-3,3,1]
 *      输出：[3,1]
 *      提示：答案 [1,2,1] 也是正确的。
 *
 * 示例 2：
 *      输入：head = [1,2,3,-3,4]
 *      输出：[1,2,4]
 *
 * 示例 3：
 *      输入：head = [1,2,3,-3,-2]
 *      输出：[1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给你的链表中可能有 1 到 1000 个节点。</li>
 *     <li>对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/8 16:56
 */
public class LC1171RemoveZeroSumConsecutiveNodesFromLinkedList_M {

    static class Solution {
        public ListNode removeZeroSumSublists(ListNode head) {
            if (head == null) {
                return null;
            }
            int sum = 0;
            // 以head作为开头，是否存在一段以 head 开头的和为 0 的连续节点，如果存在的话，删去这段节点
            for (ListNode currNode = head; currNode != null; currNode = currNode.next) {
                sum += head.val;
                //说明当前从 head 到 currNode 节点之和为0 ，这段节点都需要移除
                if (sum == 0) {
                    return removeZeroSumSublists(currNode.next);
                }
            }
            // 能到达这里说明不存在从 head 开始的一段和为0的连续节点，继续判断是否存在以 head.next 开始的一段和为0的连续节点
            head.next = removeZeroSumSublists(head.next);
            return head;
        }

        /**
         * 前缀和 + 哈希表。
         * <p>若链表中，两个节点的前缀和相等，说明这两个前缀和质检的连续节点序列的和为0，可以消去这部分连续节点。</p>
         * <p>第一次遍历链表，用哈希表记录前缀和以及对应的链表节点。对于同一前缀和s，后出现的节点覆盖前面的节点。</p>
         * <p>再次遍历链表，若当前节点 cur 的前缀和 s 在 map 中出现，说明 cur 与 map[s] 之间的所有节点和为 0，直接修改 cur 的指向，即 cur.next=map[s].next，这样就删去了这部分和为 0 的连续节点。继续往后遍历，删除所有和为 0 的连续节点。</p>
         * <p>最后返回链表的头节点 dummy.next。</p>
         */
        public ListNode removeZeroSumSublists2(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode dummyHead = new ListNode(0, head);
            ListNode currNode = dummyHead;
            int prefixSum = 0;
            Map<Integer, ListNode> map = new HashMap<>();
            while (currNode != null) {
                prefixSum += currNode.val;
                map.put(prefixSum, currNode);
                currNode = currNode.next;
            }
            prefixSum = 0;
            currNode = dummyHead;
            while (currNode != null) {
                prefixSum += currNode.val;
                currNode.next = map.get(prefixSum).next;
                currNode = currNode.next;
            }
            return dummyHead.next;
        }
    }
}
